package william.array;

/**
 * @author ZhangShenao
 * @date 2024/1/8
 * @description <a href="https://leetcode.cn/problems/merge-sorted-array/description/">...</a>
 */
public class Leetcode88_合并两个有序数组 {
    /**
     * 本质上就是归并排序的merge过程
     * 从后向前同时遍历两个数组,将较大的元素放在数组nums1的对应位置,并将相应的指针前移
     * <p>
     * 时间复杂度O(N) 两个数组各遍历一遍
     * 空间复杂度O(1)
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //边界条件校验
        if (nums2 == null || nums2.length == 0 || n <= 0) {
            return;
        }

        //从后向前同时遍历两个数组,将较大的元素放在数组nums1的对应位置,并将相应的指针前移
        int i = m - 1;
        int j = n - 1;
        int idx = nums1.length - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) {
                nums1[idx--] = nums1[i--];
            } else {
                nums1[idx--] = nums2[j--];
            }
        }

        //处理其中一个数组已经遍历完成的情况
        while (i >= 0) {
            nums1[idx--] = nums1[i--];
        }
        while (j >= 0) {
            nums1[idx--] = nums2[j--];
        }
    }
}
